#include "myTree.h"

using namespace std;

//TreeNode
TreeNode::TreeNode(char d, TreeNode* lc, TreeNode* rc, NodeTag lt, NodeTag rt){
    this->data = d;
    this->leftChild = lc;
    this->rightChild = rc;
    this->lTag = lt;
    this->rTag = rt;
}

TreeNode::~TreeNode(){
    
}

void TreeNode::printNode(){
    cout << this->data;
}



//辅助函数
TreeNode* MyTree::createTree(const char data[], int *index){//创建节点
    if (data[*index] == '\0' || data[*index] == '@'){
        return NULL;
    }
    else {
        TreeNode* p = new TreeNode(data[*index], NULL, NULL, Link, Link);
        ++(*index);
        p->leftChild = createTree(data, index);
        ++(*index);
        p->rightChild = createTree(data, index);
        return p;
    }
}

TreeNode* MyTree::copyTree(TreeNode* node){//复制树
    if (!node) {
        return nullptr;
    }

    TreeNode* newNode = new TreeNode(node->data, nullptr, nullptr, Link, Link);
    if (node->leftChild)
    {
        newNode->leftChild = copyTree(node->leftChild);
    } else newNode->leftChild = nullptr;
    if (node->rightChild)
    {
        newNode->rightChild = copyTree(node->rightChild);
    }else newNode->rightChild = nullptr;
    return newNode;
}

void MyTree::preOrder(TreeNode* node){//前序遍历
    if (node)//当前节点不为空
    {
        node->printNode();//调用输出函数输出当前节点
        preOrder(node->leftChild);//先前序遍历左子树
        preOrder(node->rightChild);//后前序遍历右子树
    }
}

void MyTree::inOrder(TreeNode* node){//中序遍历
    if (node)
    {
        inOrder(node->leftChild);
        node->printNode();
        inOrder(node->rightChild);
    }
}

void MyTree::postOrder(TreeNode* node){//后序遍历
    if (node)
    {
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        node->printNode();   
    }
}

int MyTree::leafNum(TreeNode* node){//叶子计数
    if (!node)
    {
        return 0;//如果节点为空则返回0
    }
    if (!node->leftChild && !node->rightChild)
    {
        return 1;//如果当前节点的左子节点和右子节点都为空，则当前节点是叶子节点，函数返回 1
    }
    return leafNum(node->leftChild) + leafNum(node->rightChild);//左子树叶子数量+右子树叶子数量
}//递归调用leafNum遍历左右子树

int MyTree::height(TreeNode* node){//求深度
    if (!node)
    {
        return 0;
    }
    int lch= height(node->leftChild);
    int rch= height(node->rightChild);//递归求左右子树高度
    return ((lch > rch) ? lch : rch)+1;//返回左右子树高度较大值+根节点高度1
}

TreeNode *pre = nullptr;
void MyTree::inThreading(TreeNode* p){//线索化
	// pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
    if (p != nullptr)
    {
        inThreading(p->leftChild);//递归遍历让左子树线索化
        if (p->leftChild == nullptr)//如果无左孩子
        {
            p->lTag = Thread;//表示此为线索而非孩子指针
            p->leftChild = pre;//设置左指针直线前驱节点
        }
        if (pre != nullptr && pre->rightChild == nullptr)//pre 不为空且 pre 的右孩子为空
        {
            pre->rightChild = p;//右指针指向当前节点
            pre->rTag = Thread;//线索化
        }
        pre = p;//更新p的前驱节点为p，进行下一个的线索化
        inThreading(p->rightChild);
        
    }
}

void MyTree::inOrderTraverse_Thr(TreeNode* node){//中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
    TreeNode* p = node;
    if(p)
        while(p->leftChild != nullptr)
            p = p->leftChild;//找到p的最左节点
    TreeNode tmp = *p;
    while (&tmp != nullptr)
    {
        tmp.printNode();
        if (tmp.rightChild != nullptr)
        {
            tmp = this->nextNode(tmp);
        }
        else break;
        
    }
}

TreeNode* MyTree::locate(TreeNode* node,const char& c){
    if (node->data == c)
    {
        return node;
    }
    
    if (node->leftChild && node->lTag != Thread)
    {
        TreeNode* p = locate(node->leftChild, c);
        if (p)
        {
            return p;
        }
        
    }

    if (node->rightChild && node->rTag != Thread)
    {
        TreeNode* p = locate(node->rightChild, c);
        if (p)
        {
            return p;
        }
        
    }
    return nullptr;
}

TreeNode* MyTree::inOrderFisrtNode(TreeNode* node){
    TreeNode* tmp = node;
    while (tmp->lTag == Link)
    {
        tmp = tmp->leftChild;
    }
    return tmp;
}

TreeNode* MyTree::inOrderLastNode(TreeNode* node){
    TreeNode* tmp = node;
    while (tmp->rTag == Link)
    {
        tmp = tmp->rightChild;
    }
    
    return tmp;
}


//MyTree
MyTree::MyTree(){//无参构造
    this->root = nullptr;
    this->isThread = false;
}

MyTree::MyTree(const char c[]){//构造函数
    int i = 0;
    root = createTree(c, &i);
    isThread = false;
}

MyTree::MyTree(const MyTree& T){//拷贝函数
    root = copyTree(T.root);
    isThread = T.isThread;
}

MyTree::~MyTree(){//析构函数

}

void MyTree::preOrderTraverse(){//前序遍历
    TreeNode* temp=root;
    if(this->isThread==false){//如果不是线索二项树
        preOrder(temp);//调用前序遍历函数从temp即root处开始前序遍历
    }
}

void MyTree::inOrderTraverse(){//中序遍历
    TreeNode* tmp = root;
    if (this->isThread == false){
        inOrder(tmp);
    }
    else{
        inOrderTraverse_Thr(tmp);
        // inOrder(tmp);
    }
}

void MyTree::postOrderTraverse(){//后序遍历
    if (this->isThread == false)
    {
        TreeNode* tmp = root;
        postOrder(tmp);
    }
}

int MyTree::countLeaf(){//叶结点计数
    if (this->isThread == false)
    {
        TreeNode* tmp = root;
        return leafNum(tmp);//返回叶结点计数函数值（从root开始
    }
    return 0;
}

int MyTree::countHeight(){//计算树的深度
    if (this->isThread == false)
    {
        TreeNode* tmp = root;
        return height(tmp);//返回计算深度函数值
    }
    return 0; 
}

bool MyTree::isThreadedTree(){//判断是否为线索二叉树
    return this->isThread;
}

bool  MyTree::inOrderThreading(){//线索化
    this->isThread = true;
    TreeNode* tmp = root;
    inThreading(tmp);
    return this->isThread;
}

TreeNode&  MyTree::locateNode(const char& d){//结点定位
    TreeNode* tmp = root;
    return *locate(tmp, d);
}

TreeNode&  MyTree::preNode(const TreeNode& node){//获取前驱结点
    TreeNode* p = node.leftChild;
    if (this->isThread == false)
    {
        this->inOrderThreading();
    }
    // 如果ltag=0，则p的后继为以该节点为根的左子树上按中序遍历的最后一个节点
    if (node.lTag == Link)
    {
        return *(inOrderLastNode(p));
        
    }
    else return *(node.leftChild);       
}

TreeNode&  MyTree::nextNode(const TreeNode& node){//获取后继结点
    TreeNode* p = node.rightChild;
    
    if (this->isThread == false)
    {
        this->inOrderThreading();
    }
    // 如果rtag=0，则p的后继为以该节点为根的右子树上按中序遍历的第一个节点
    if (node.rTag == Link)
    {
        return *(inOrderFisrtNode(p));   
    }
    else return *(node.rightChild);
}



//HuffmanTree
HuffmanTree::HuffmanTree(const int& n,const int data[]){//构造函数
    this->num = n;
    this->HFT = new HFNode[n* 2];
    int* p = new int[n];
    for (int i = 0; i < n; i++)
    {
        p[i] = data[i];
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (p[j] < p[j + 1])
            {
                int tmp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = tmp;
            }
        }
    }
    initleaves(n, p);
    generateCodes(n*2 - 1, "");
    // showHFT(this->num);
}

HuffmanTree::~HuffmanTree(){//析构函数
    
}

void HuffmanTree::printHuffmanCodes(){
    int n = this->num;
    for (int j = 1; j <= n; j++)
    {
        cout<<HFT[j].weight<<":"<<HFT[j].code<<endl;
    }
}

//辅助函数
void HuffmanTree::selectMin(HFNode* hft, int n, int &s1, int &s2){
    for(int i = 1; i < n; i++){         //初始化s1，s1的双亲为0
        if(HFT[i].parent == 0){     
            s1 = i;
            break;        
        }
    }

    for(int i = 1; i < n; i++){         //s1为权值最小的下标
        if(HFT[i].parent == 0 && HFT[s1].weight > HFT[i].weight)
            s1 = i;
    }

    for(int j = 1; j < n; j++){         //初始化s2，s2的双亲为0
        if(HFT[j].parent == 0 && j != s1){
            s2 = j;
            break;
        }
    }

    for(int j = 1; j < n; j++){         //s2为另一个权值最小的下标
        if(HFT[j].parent == 0 && HFT[s2].weight > HFT[j].weight && j != s1)
            s2 = j;
    }
}

void HuffmanTree::initleaves(int n, const int* data){
    if(n <= 1) return;
	int m = 2*n - 1;            //数组共2n - 1个元素
    for(int i = 1; i <= m; i++){
        HFT[i].parent = 0;
        HFT[i].left = 0;
        HFT[i].right = 0;
    }
	for(int i = 1; i <= n; i++)
        HFT[i].weight = data[i - 1];
    for(int i = n + 1; i <= m; i++)         //产生的新结点要放在从n+1开始，一直到2n-1的位置
    {
        int s1, s2;
        selectMin(HFT, i, s1, s2);
        HFT[s1].parent = i;
        HFT[s2].parent = i;   //相当于从表F中删除s1, s2
        HFT[i].left = s1;
        HFT[i].right = s2;
        HFT[i].weight = HFT[s1].weight + HFT[s2].weight;
    }
}

void HuffmanTree::showHFT(int n){
    cout << "index  weight  parent  LTree  RTree" << endl;
    cout << left;     //左对齐输出
    int m = 2*n - 1;
    for(int i = 1; i <= m; i++){
        cout << i << "  ";                       
        cout << HFT[i].weight << "  ";     
        cout << HFT[i].parent << "  ";
        cout << HFT[i].left << "  ";
        cout << HFT[i].right << "  ";
        cout << HFT[i].code << "  " << endl;
    }
}

void HuffmanTree::generateCodes(int idx, string code){
    HFT[idx].code = code;
    if (HFT[idx].left != 0)
    {
        generateCodes(HFT[idx].left, code + "0");
    }
    if (HFT[idx].right != 0)
    {
        generateCodes(HFT[idx].right, code + "1");
    }
}
